home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / ENV Server / server src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-31  |  6.0 KB  |  191 lines  |  [TEXT/ALFA]
  1. /***************************************************
  2. *                                                  *
  3. *  hash.c                                          *
  4. *                                                  *
  5. *  This contains all the routines to manage the    *
  6. *  hash table.                                     *
  7. *                                                  *
  8. ***************************************************/
  9.  
  10. #include <MacHeaders>
  11. #include <string.h>
  12. #include "hash.h"
  13.  
  14.  
  15. #define DEBUG_HASH 0               /* != 0 for debugging purposes */
  16.  
  17. static int hash_add_node(HashNodePtr);
  18. static int hash_get_key(char *);
  19.  
  20. static HashTablePtr gTable=NULL;
  21.  
  22. /**********************************************************
  23. *                                                         *
  24. *  hash_add_entry()                                       *
  25. *                                                         *
  26. *  This routine accepts the table to add a new node to.   *
  27. *  The node's name, type, and line number are also passed *
  28. *  here.                                                  *
  29. *                                                         *
  30. **********************************************************/
  31. int hash_add_entry(char *name)
  32. {
  33.   HashNodePtr node;
  34.   char *eqp;    /* ptr to equals sign/string after '=' sign */
  35.   
  36.   if ( (eqp = strchr(name, '=')) == NULL)
  37.     return H_ERROR;
  38.   node = (HashNodePtr) NewPtr( sizeof( HashNode));
  39.   if (node == NULL)
  40.     return H_ERROR;
  41.   
  42.   *eqp++ = '\000';   /* change '=' to string terminator; expr is divided now */
  43.   node->name  = NewPtrClear( strlen(name)+1);
  44.   if (node->name == NULL)
  45.   {
  46.       DisposPtr( (Ptr)node);
  47.       return(H_ERROR);
  48.   }
  49.   node->value = NewPtrClear( strlen(eqp)+1);
  50.   if (node->value == NULL)
  51.   {
  52.       DisposPtr (node->name);
  53.       DisposPtr ((Ptr)node);
  54.       return(H_ERROR);
  55.   }
  56.   strcpy( node->name, name);
  57.   strcpy( node->value, eqp);
  58.   node->key = hash_get_key(node->name);
  59.   node->next_node = NULL;
  60.   return hash_add_node( node);
  61. } /* hash_add_entry */
  62.  
  63.  
  64. /******************************************************************
  65. *                                                                 *
  66. *  hash_add_node()                                                *
  67. *                                                                 *
  68. *  This routine accepts a pointer to a hash table and a pointer   *
  69. *  to a hash table node and adds that node to the table.          *
  70. *  Entries are stored in the buckets in an alphabetic order(A-Z). *
  71. *                                                                 *
  72. ******************************************************************/
  73. static int hash_add_node(HashNodePtr node)
  74. {
  75.   HashNodePtr here, last;
  76.   
  77.   if (gTable == NULL)
  78.     gTable = (HashTablePtr)NewPtrClear(sizeof( HashTable));
  79.   here = gTable->buckets[node->key];
  80.   last=NULL;
  81.   while (here != NULL)
  82.   {
  83.     int order = strcmp(here->name, node->name);
  84.     
  85.     if (order < 0)
  86.     {
  87.         last = here;
  88.         here = here->next_node;
  89.     }
  90.     else
  91.     {
  92.         if (order == 0)   /* then it's already in the table; redefine it */
  93.         {
  94.             node->next_node = here->next_node;
  95.             if (last == NULL)
  96.                 gTable->buckets[node->key] = node;
  97.             else
  98.                 last->next_node = node;
  99.             
  100.             DisposPtr(here->name);      /* delete the old definition */
  101.             DisposPtr(here->value);
  102.             DisposPtr((Ptr)here);
  103.             return(H_NOERR);
  104.         }
  105.         else
  106.             break;
  107.     }
  108.   } /* while */
  109.   if (last == NULL)
  110.   {
  111.     node->next_node = gTable->buckets[node->key];
  112.     gTable->buckets[node->key] = node;
  113.   }
  114.   else  /** put node after last if last != NULL */
  115.   {
  116.     node->next_node = last->next_node;
  117.     last->next_node = node;
  118.   }
  119.   
  120.   /** save the last referenced node in the table info for a quick lookup **/
  121.   gTable->last_key  = node->key;
  122.   gTable->last_node = node;
  123.   return(H_NOERR);
  124. } /* hash_add_node */
  125.  
  126.  
  127. /***************************************************************
  128. *                                                              *
  129. *  hash_get_entry()                                            *
  130. *                                                              *
  131. *  This routine fetches the node that contains name from the   *
  132. *  table pointed to by table.                                  *
  133. *  It returns the pointer to the node if name is in the table. *
  134. *  Otherwise, it returns NULL if name cannot be found.         *
  135. *                                                              *
  136. ***************************************************************/
  137. HashNodePtr hash_get_entry(char *name)
  138. {
  139.   HashNodePtr here;
  140.   int key;
  141.   
  142.   key = hash_get_key(name);
  143.   
  144.   /** before we search the buckets, search the last accessed node. **/
  145.   if (gTable->last_key == key)
  146.     if ((gTable->last_node != NULL) && !strcmp(gTable->last_node->name, name))
  147.       /** then the last accessed node is the one we want **/
  148.       return(gTable->last_node);
  149.   /** else search the buckets */
  150.  
  151.   here = gTable->buckets[key];
  152.   while ((here!= NULL) && strcmp(here->name, name))
  153.   {
  154.     here = (HashNodePtr)here->next_node;
  155.   }
  156.   if (here != NULL)  /* then save this node in the last accessed fields */
  157.   { gTable->last_node = here;
  158.     gTable->last_key = key;
  159.   }
  160.   return(here);
  161. } /* hash_get_entry */
  162.  
  163.  
  164. /*****************************************************************
  165. *                                                                *
  166. *  hash_get_key()                                                *
  167. *                                                                *
  168. *  This routine calculates the hashing key for the string passed *
  169. *  to it.  It returns the key.                                   *
  170. *  This hashing algorithm is from Aho, Sethi, Ullman - Compilers *
  171. *  Principles, Techniques and Tools  (The dragon book).          *
  172. *                                                                *
  173. *****************************************************************/
  174. static int hash_get_key(char *s)
  175. {
  176.   char *p;
  177.   unsigned long h=0, g;
  178.   for (p=s; *p != '\0'; p++)
  179.   {
  180.     h = (h << 4) + *p;
  181.     if ( g = h&0xf0000000)
  182.     {
  183.       h = h^(g>>12);
  184.       h = h^g;
  185.     }
  186.   }
  187.   return( h % HASH_SIZE);
  188. } /* hash_get_key */
  189.  
  190.  
  191.